variable-order markov models

Page numbers are for draft copy at present; they will be replaced with correct numbers when final book is formatted. Chapter numbers are correct and will not change now.

While a simple Markov model only uses the last state/token to predict the next one, a variable-order Markov model may use several past states. For example a third-order Markov model, gives the probabilty of the state S_t as a function of the last three states:
      P(S_t=s)   =   f(s_t-1,s_t-2,s_t-3)

Defined on page 325

Used on Chap. 14: page 325